package com.hyper_yang.algorithmRecord;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

// leetcode 621 任务调度器
public class LeetCode_621 {
    /*
    给你一个用字符数组 tasks表示的 CPU需要执行的任务列表，用字母 A到 Z表示，以及一个冷却时间 n。
    每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个相同种类的任务之间必须有长度为 n的冷却时间。
    返回完成所有任务所需要的最短时间间隔
     */
    // 方法一: 模拟法
    public static int leastInterval1(char[] tasks, int n) {
        // 统计每个任务出现的次数
        HashMap<Character, Integer> countMap = new HashMap<>();
        for (char task : tasks)
            countMap.put(task, countMap.getOrDefault(task, 0) + 1);
        // 取任务种类数量
        int t = countMap.size();
        // 定义两个状态列表
        ArrayList<Integer> restCount = new ArrayList<>(countMap.values()); // 任务剩余次数
        ArrayList<Integer> nextAvailableTime = new ArrayList<>(Collections.nCopies(t, 1)); // 任务下一次可执行时间
        // 模拟 CPU时钟
        int time = 0;
        // 遍历任务选择执行
        for (int i = 0; i < tasks.length; i++) {
            time++;
            int minNextAvailableTime = Integer.MAX_VALUE;
            // 1、获取所有任务中最早可执行的时间
            for (int j = 0; j < t; j++) {
                // 取还没做完的任务
                if (restCount.get(j) != 0)
                    minNextAvailableTime = Math.min(minNextAvailableTime, nextAvailableTime.get(j));
            }
            // 2、直接推进时间，指定任务
            time = Math.max(time, minNextAvailableTime);
            // 3、选取可执行任务中，剩余次数最多的那个执行
            int maxRestCountTask = -1; // 保存要执行任务的索引
            for (int j = 0; j < t; j++) {
                if (restCount.get(j) > 0 && nextAvailableTime.get(j) <= time)
                    // 如果比之前保存的最大剩余任务书还大，就更新
                    if (maxRestCountTask == -1 || restCount.get(j) > restCount.get(maxRestCountTask))
                        maxRestCountTask = j;
            }
            // 4、执行任务，更新状态列表
            nextAvailableTime.set(maxRestCountTask, time + n + 1);
            restCount.set(maxRestCountTask, restCount.get(maxRestCountTask) - 1);
        }

        return time;
    }

    // 方法二: 构造法
    public static int leastInterval(char[] tasks, int n) {
        // 统计每个任务出现的次数
        HashMap<Character, Integer> countMap = new HashMap<>();
        for (char task : tasks)
            countMap.put(task, countMap.getOrDefault(task, 0) + 1);
        // 取任务种类数量
        int t = countMap.size();

        int maxCount = 0;
        int maxNum = 0;

        // 计算 maxCount
        for (int count : countMap.values())
            maxCount = Math.max(maxCount, count);
        // 计算 maxNum
        for (char task : countMap.keySet())
            if (countMap.get(task) == maxCount)
                maxNum++;

        return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxNum);
    }

    public static void main(String[] args) {
        System.out.println(leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B'}, 2)); // 8
        System.out.println(leastInterval(new char[]{'A', 'C', 'A', 'B', 'D', 'B'}, 1)); // 6
    }
}
